/**
 * 1026. 节点与其祖先之间的最大差值
 * https://leetcode-cn.com/problems/maximum-difference-between-node-and-ancestor/
 */
public class Solutions_1026 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(3);
        root.right = new TreeNode(10);
        root.right.right = new TreeNode(14);
        root.right.right.left = new TreeNode(13);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(6);
        root.left.right.left = new TreeNode(4);
        root.left.right.right = new TreeNode(7);  // output: 8 - 1 = 7

        int result = maxAncestorDiff(root);
        System.out.println(result);
    }

    private static int res = Integer.MIN_VALUE;
    // 转化为：计算根节点到每个叶子节点上的最大值与最小值之间的差
    public static int maxAncestorDiff(TreeNode root) {
        dfs(root, root.val, root.val);
        return res;
    }

    public static void dfs(TreeNode root, int minVal, int maxVal) {
        if (root == null) {
            return;
        }
        // 当前节点值，参与比较所属路径中的最大值，最小值
        maxVal = Math.max(maxVal, root.val);
        minVal = Math.min(minVal, root.val);
        if (root.left == null && root.right == null) {
            // 叶子节点时，比较得到最大值，并 return
            res = Math.max(res, maxVal - minVal);
            return;
        }
        // 递归左右子树
        dfs(root.left, minVal, maxVal);
        dfs(root.right, minVal, maxVal);
    }
}
